//234 Palindrome Linked List
/*
以 O(1) 的空间复杂度，判断链表是否回文

输入是一个链表，输出是一个布尔值，表示链表是否回文
Input: 1->2->3->2->1
Output: true

先用快慢指针找到链表中点，再把链表切为两半，把后半段翻转，对比两个片段是否相同
*/
// 主函数
bool isPalindrome(ListNode *head)
{
	if (!head || !head->next)
	{
		return true;
	}

	ListNode *slow = head, *fast = head;
	while (fast->next && fast->next->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}

	//
	slow->next = reverseList(slow->next);
	slow = slow->next;
	while (slow)
	{
		if (head->val != slow->val)
		{
			return false;
		}
		head = head->next;
		slow = slow->next;
	}
	return true;
}
// 辅函数
ListNode *reverseList(ListNode *head)
{
	ListNode *prev = nullptr, *next;
	while (head)
	{
		next = head->next;
		head->next = prev;
		prev = head;
		head = next;
	}
	return prev;
}

//83
//328
//19
//148
